import java.util.Arrays;

public class Solution300 {
    /**
     * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
     * <p>
     * 示例:
     * <p>
     * 输入: [10,9,2,5,3,7,101,18]
     * 输出: 4
     * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
     */

    // 定义dp[i]为以i结尾的最长升序字串
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    maxval = Math.max(maxval, dp[j]);
                }
            }
            dp[i] = maxval + 1;
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }

    // tails[i] 为长度为i + 1的递增子序列末位数最小值
    public int lengthOfLIS2(int[] nums) {
        int[] tails = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = 0, j = len;
            while (i < j) {
                int m = (i + j) >> 1;
                if (tails[m] < num) {
                    i = m + 1;
                } else j = m;
            }
            tails[i] = num;
            if (len == j) {
                len++;
            }
        }
        return len;
    }
}
